lower bound with bisect_left (python)

description: 이진탐색에 활용하는 lower bound를 파이썬에서는 `bisect.bisect_left`로 가능하다.
aliases: No value
tags: No value
created: 2023-05-18T17:32:42
updated: 2023-08-11T13:40:39
title: lower bound with bisect_left (python)

bisect.bisect_left

C++에 lower_bound가 있다면 파이썬에는 bisect.bisect_left가 있다. 그럼 upper_bound는? bisect.bisect_right 바보야 😲

이분탐색은 그 자체로 너무 많은 곳에 활용이 되고 있어서 실전 위주로 정리를 해보겠다. 흠흠

아래는 LIS 가장 긴 증가하는 부분수열를 파이썬으로 구현한 코드이다. 확실히 엄청나게 간결하다.

LIS 가장 긴 증가하는 부분수열
https://choiwheatley.notion.site/LIS-d61b26f5619a4ea1b0412155535ec812 에 정리해두긴 했으나 수정할 사안이 존재하여 다시 불러왔다.

아래는 삽입정렬을 bisect_left를 활용하여 푼 코드이다. 부분정렬리스트인데, 이분탐색을 안할 이유가 없잖아?

from bisect import bisect_left


def insertion_sort(data):
    """insertion sort with binary search => O(N LOG(N))"""

    result = []

    for e in data:
        idx = bisect_left(result, e)
        if idx == len(result):
            result.append(e)
        else:
            result.insert(idx, e)

    return result


ls = [199, 22, 33, 12, 32, 64, 72, 222, 233]
assert sorted(ls) == insertion_sort(ls)